package leecode

func trap(height []int) int {
	stack := make([]int, 0)
	stack = append(stack, 0)
	var result int
	for i := 1; i < len(height); i++ {
		//栈顶元素的下标
		topIndex := stack[len(stack)-1]
		//如果当前元素大于栈顶元素
		if height[i] > height[topIndex] {
			for len(stack) != 0 && height[i] > height[topIndex] {
				//先将当前栈顶元素弹出
				stack = stack[:len(stack)-1]
				if len(stack) != 0 {
					//最小的高 中间元素即为栈顶元素
					h := min(height[i], height[stack[len(stack)-1]]) - height[topIndex]
					//最小的宽
					w := i - stack[len(stack)-1] - 1
					result += h * w
					topIndex = stack[len(stack)-1]
				}
			}
			stack = append(stack, i)
		} else {
			stack = append(stack, i)
		}
	}
	return result
}
